﻿// Node of a vector tree, where the vector index is a long
//
// Copyright (C) 2012 M. de Wolde
//
// This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
// details.
//
// You should have received a copy of the GNU Lesser General Public License along with this program. If not, see
// <http://www.gnu.org/licenses/>.
//
// 2012-07-18 MIWO Created.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using System.Text;

namespace Lemody.Glu {

/// <summary>Node of a vector tree, where the vector index is a long.</summary>
[SerializableAttribute]
public class LongVectorNode<T>
{
    // See the comments in class LongVector. The LongVectorNode uses a long when long indexing is performed, and uses
    // Int16 or Int32 when a short or int is intended regardless whether the node is a VectorNode or LongVectorNode.

    // Constants.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Indicates that the node is left heavy or right heavy, but still sufficiently balanced.</summary>
    /// <remarks>Indicates that the subtrees differ in height by 1.</remarks>
    private const Int16 FlagHeavy = 1;

    /// <summary>Indicates a node imbalance.</summary>
    /// <remarks>Indicates that the subtrees differ in height by 2.</remarks>
    private const Int16 FlagImbalance = 2;

    /// <summary>Indicates that the heavy or imbalance flag is to the left; else it is to the right.</summary>
    private const Int16 FlagLeftHeavyOrImbalance = 4;

    /// <summary>Mask for the flags used by the node.</summary>
    private const Int16 NodeFlagsMask = FlagHeavy | FlagImbalance | FlagLeftHeavyOrImbalance;

    /// <summary>Balance value if the height of the left subtree is two more than the height of the right subtree.</summary>
    private const Int32 LeftImbalance = -2;

    /// <summary>Balance value if the height of the left subtree is one more than the height of the right subtree.</summary>
    private const Int32 LeftHeavy = -1;

    /// <summary>Balance value if the height of the left subtree is equal to the height of the right subtree.</summary>
    private const Int32 Balanced = 0;

    /// <summary>Balance value if the height of the right subtree is one more than the height of the left subtree.</summary>
    private const Int32 RightHeavy = 1;

    /// <summary>Balance value if the height of the right subtree is two more than the height of the left subtree.</summary>
    private const Int32 RightImbalance = 2;

    // Fields.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Number of nodes in the subtree started by the node, including 1 for the node itself.</summary>
    private long _count;

    /// <summary>Element associated with the node.</summary>
    private T _element;

    /// <summary>Reference to the parent node, null for the root node.</summary>
    private LongVectorNode<T> _parentNode;

    /// <summary>Left subnode, or null.</summary>
    private LongVectorNode<T> _leftSubnode;

    /// <summary>Right subnode, or null.</summary>
    private LongVectorNode<T> _rightSubnode;

    /// <summary>Information flags.</summary>
    private short _flags;

    // Object management.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Constructor.</summary>
    /// <remarks>An internal default constructor is provided such that the application cannot instantiate vector nodes.</remarks>
    internal LongVectorNode()
    {
        //
    }

    // Properties.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Number of nodes in the subtree, the node itself included.</summary>
    internal long LongCount
    {
        [DebuggerStepThrough]
        set
        {
            _count = value;
        }
        [DebuggerStepThrough]
        get
        {
            return _count;
        }
    }

    /// <summary>Element associated with the node.</summary>
    public T Element
    {
        [DebuggerStepThrough]
        set
        {
            _element = value;
        }
        [DebuggerStepThrough]
        get
        {
            return _element;
        }
    }

    /// <summary>Left subnode, or null.</summary>
    internal LongVectorNode<T> Left
    {
        [DebuggerStepThrough]
        get
        {
            return _leftSubnode;
        }
    }

    /// <summary>Right subnode, or null.</summary>
    internal LongVectorNode<T> Right
    {
        [DebuggerStepThrough]
        get
        {
            return _rightSubnode;
        }
    }

    /// <summary>Returns the height of the subtree started by the node.</summary>
    /// <returns>Returns 1 at least, for the node itself.</returns>
    internal Int32 GetHeight()
    {
        Int32 levelCount = 1;
        if (Balance > 0)
        {
            Debug.Assert(_rightSubnode != null);
            levelCount += _rightSubnode.GetHeight();
        }
        else
        {
            if (_leftSubnode != null)
            {
                levelCount += _leftSubnode.GetHeight();
            }
        }
        return levelCount;
    }

    /// <summary>Returns the index in the vector, of the node and the element in the node.</summary>
    public long GetIndex()
    {
        long index = _leftSubnode == null? 0: _leftSubnode._count;
        LongVectorNode<T> node = this;
        LongVectorNode<T> parentNode = _parentNode;
        while (node != null && parentNode != null)
        {
            if (ReferenceEquals(parentNode._rightSubnode, node))
            {
                index++;
                if (parentNode._leftSubnode != null)
                {
                    index += parentNode._leftSubnode._count;
                }
            }
            node = parentNode;
            parentNode = node._parentNode;
        }
        return index;
    }

    // Add and remove elements.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Inserts an element in the subtree started by the node.</summary>
    /// <param name="index">I: Index where to insert, 0-based.</param>
    /// <param name="leftSkipped">I: Number of elements skipped in nodes and subtrees on the left.</param>
    /// <param name="element">I: Element to insert.</param>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: Node that starts the subtree where to insert, or null for a yet empty subtree.</param>
    /// <param name="heightChange">O: Change of the height of the current tree, 0 or 1.</param>
    /// <returns>Returns the new node containing the inserted element.</returns>
    internal static LongVectorNode<T> Insert(long index, long leftSkipped, T element, LongVectorNode<T> parentNode, ref LongVectorNode<T> node,
        out Int32 heightChange)
    {
        LongVectorNode<T> resultNode;
        if (node == null)
        {
            // Index where to insert reached; insert.
            node = new LongVectorNode<T>();
            node._element = element;
            node._parentNode = parentNode;
            node._count++;
            heightChange = 1;
            resultNode = node;
        }
        else
        {
            // Insert in a subtree.
            long leftCount = node._leftSubnode == null? 0: node._leftSubnode._count;
            long currentIndex = leftSkipped + leftCount;
            bool left;
            if (index <= currentIndex)
            {
                left = true;
                resultNode = Insert(index, leftSkipped, element, node, ref node._leftSubnode, out heightChange);
            }
            else
            {
                left = false;
                resultNode = Insert(index, leftSkipped + leftCount + 1, element, node, ref node._rightSubnode, out heightChange);
            }
            node._count++;
            // Adjust the balance.
            if (heightChange == 1)
            {
                // Adjust the balance value.
                node.AdjustBalance(heightChange, left);
                if (node.Balance == 0)
                {
                    // The height change is absorbed by the current node; cancel the height change.
                    heightChange = 0;
                }
                else
                {
                    // Allow to rebalance. The method may or may not rebalance. If it rebalances this may or may
                    // decrement the tree height. A decrement is returned as a height change of -1, which is added to
                    // the current height change, which cancels the height change. Else the height change propagates to
                    // the caller.
                    heightChange += node.Rebalance(parentNode, ref node);
                }
            }
            else
            {
                Debug.Assert(heightChange == 0);
            }
        }
        return resultNode;
    }

    /// <summary>Returns the successor node, removing it from its current location.</summary>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: Node, not null.</param>
    /// <param name="heightChange">O: Height change, -1 for a reduction of one level, else 0.</param>
    private static LongVectorNode<T> RemoveSuccessor(LongVectorNode<T> parentNode, ref LongVectorNode<T> node, out Int32 heightChange)
    {
        LongVectorNode<T> successor;
        bool removedFromSubtree;
        if (node._leftSubnode == null)
        {
            // The successor node with the smallest index in the right subtree of the target node is found. Remove the successor node.
            // If the successor node has a right subtree let that subtree take the position of the successor node.
            successor = node;
            node = node._rightSubnode;
            heightChange = -1;
            removedFromSubtree = false;

            // Update the parent of the promoted node.
            if (node != null)
            {
                node._parentNode = parentNode;
            }
        }
        else
        {
            // Continue the walk in the left subtree, looking for the successor.
            successor = RemoveSuccessor(node, ref node._leftSubnode, out heightChange);
            if (heightChange == -1)
            {
                node.AdjustBalance(heightChange, true);
            }
            else
            {
                Debug.Assert(heightChange == 0);
            }
            removedFromSubtree = true;
        }

        if (removedFromSubtree)
        {
            node._count--;
            Debug.Assert(node._count > 0);

            // Rebalance, if necessary.
            if (heightChange != 0)
            {
                if (node.Balance != 0)
                {
                    heightChange = node.Rebalance(parentNode, ref node);
                }
            }
        }
        return successor;
    }

    /// <summary>Deletes the identified element from the tree.</summary>
    /// <param name="index">I: Index of the element to delete, 0-based.</param>
    /// <param name="leftSkipped">I: Number of elements skipped in nodes and subtrees on the left.</param>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: Node, not null.</param>
    /// <param name="heightChange">O: Height change, -1 for a reduction of one level, else 0.</param>
    /// <returns>Returns the deleted element.</returns>
    internal static T Delete(long index, long leftSkipped, LongVectorNode<T> parentNode, ref LongVectorNode<T> node, out Int32 heightChange)
    {
        Debug.Assert(node != null);
        bool deletedFromSubtree;
        long leftCount = node._leftSubnode == null? 0: node._leftSubnode._count;
        long currentIndex = leftSkipped + leftCount;
        T element;
        if (currentIndex == index)
        {
            // Target node found.
            element = node._element;
            bool leftNull = node._leftSubnode == null;
            bool rightNull = node._rightSubnode == null;
            if (leftNull && rightNull)
            {
                // The node is a leaf. There are no subtrees to handle, just delete the node.
                node = null;
                heightChange = -1;
                deletedFromSubtree = false;
            }
            else if (leftNull || rightNull)
            {
                // The node has one subtree. Let that subtree take the position of the current node, deleting the current node.
                if (leftNull)
                {
                    node = node._rightSubnode;
                }
                else
                {
                    node = node._leftSubnode;
                }
                heightChange = -1;
                deletedFromSubtree = false;
                // Update the parent of the promoted node.
                node._parentNode = parentNode;
            }
            else
            {
                // The node has two subtrees. Delete the current node by replacing it with the successor node. The
                // successor is the node in the right subtree and then the leftmost node on each level until at a leaf.
                LongVectorNode<T> successor = RemoveSuccessor(node, ref node._rightSubnode, out heightChange);
                successor._count = node._count;
                successor._flags = node._flags;
                successor._leftSubnode = node._leftSubnode;
                node._leftSubnode = null;
                successor._rightSubnode = node._rightSubnode;
                node._rightSubnode = null;
                node._parentNode = null;
                successor._parentNode = parentNode;
                node._element = default(T);
                node = successor;
                if (node._leftSubnode != null)
                {
                    node._leftSubnode._parentNode = node;
                }
                if (node._rightSubnode != null)
                {
                    node._rightSubnode._parentNode = node;
                }
                node.AdjustBalance(heightChange, false);
                deletedFromSubtree = true;
            }
        }
        else
        {
            // Delete from a subtree.
            bool left;
            if (index < currentIndex)
            {
                left = true;
                element = Delete(index, leftSkipped, node, ref node._leftSubnode, out heightChange);
            }
            else
            {
                left = false;
                element = Delete(index, leftSkipped + leftCount + 1, node, ref node._rightSubnode, out heightChange);
            }
            if (heightChange == -1)
            {
                node.AdjustBalance(heightChange, left);
            }
            else
            {
                Debug.Assert(heightChange == 0);
            }
            deletedFromSubtree = true;
        }

        if (deletedFromSubtree)
        {
            node._count--;
            Debug.Assert(node._count > 0);

            // Rebalance, if necessary.
            if (heightChange != 0)
            {
                if (node.Balance != 0)
                {
                    heightChange = node.Rebalance(parentNode, ref node);
                }
            }
        }

        return element;
    }

    /// <summary>Clears the subtree started by the node.</summary>
    /// <remarks>
    ///     The method deletes nodes recursively, setting all node references to null, and setting the value in each
    ///     node to the default for the type. If the type is a reference type this sets the value to null.
    /// </remarks>
    internal void ClearSubtree()
    {
        _element = default(T);
        _parentNode = null;
        if (_leftSubnode != null)
        {
            _leftSubnode.ClearSubtree();
            _leftSubnode = null;
        }
        if (_rightSubnode != null)
        {
            _rightSubnode.ClearSubtree();
            _rightSubnode = null;
        }
    }

    // Maintain the tree structure.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Node balance.</summary>
    /// <remarks>
    ///     <para>
    ///         The balance is -1 if the node is left-heavy, meaning that the height of the left subtree is one more
    ///         than the height of the right subtree. The balance is 0 if the subtrees are of equal height and the
    ///         balance is 1 if the node is right-heavy.
    ///     </para>
    ///     <para>
    ///         Internally also the values -2 and 2 occur, when the heights of the subtrees differ by two. This leads to
    ///         rebalancing and the application may expect the values -1, 0 and 1 only.
    ///     </para>
    /// </remarks>
    internal Int32 Balance
    {
        private set
        {
            Debug.Assert(value >= -2 && value <= 2);
            Int32 flags = _flags & ~NodeFlagsMask;
            if (value == -1 || value == 1)
            {
                flags |= FlagHeavy;
            }
            else if (value == -2 || value == 2)
            {
                flags |= FlagImbalance;
            }
            if (value < 0)
            {
                flags |= FlagLeftHeavyOrImbalance;
            }
            _flags = (short) (flags);
        }
        get
        {
            Int32 balance;
            if ((_flags & FlagHeavy) != 0)
            {
                balance = 1;
            }
            else if ((_flags & FlagImbalance) != 0)
            {
                balance = 2;
            }
            else
            {
                balance = 0;
            }
            if ((_flags & FlagLeftHeavyOrImbalance) != 0)
            {
                Debug.Assert(balance != 0);
                balance = -balance;
            }
            return balance;
        }
    }

    /// <summary>Adjusts the balance on the node given the height change and given the direction.</summary>
    /// <param name="heightChange">I: Height change, -1 for a decrement, 1 for an increment, 0 if there is no change.</param>
    /// <param name="left">I: True if the height of the left subtree changed, false if the height of the right subtree changed.</param>
    private void AdjustBalance(Int32 heightChange, bool left)
    {
        if (heightChange == -1)
        {
            if (left)
            {
                Int32 balance = Balance + 1;
                Debug.Assert(balance <= 2);
                Balance = balance;
            }
            else
            {
                Int32 balance = Balance - 1;
                Debug.Assert(balance >= -2);
                Balance = balance;
            }
        }
        else if (heightChange == 1)
        {
            if (left)
            {
                Int32 balance = Balance - 1;
                Debug.Assert(balance >= -2);
                Balance = balance;
            }
            else
            {
                Int32 balance = Balance + 1;
                Debug.Assert(balance <= 2);
                Balance = balance;
            }
        }
        else
        {
            Debug.Assert(heightChange == 0);
        }
    }

    /// <summary>Corrects an inbalance by performing a single rotation.</summary>
    /// <param name="left">I: True if the subnode direction is left, false if the direction is right.</param>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: Node.</param>
    /// <returns>
    ///     The method returns the change of height of the current tree. The change is -1 for a decrement of the tree
    ///     height. The change is 0 if the tree height is not decremented. A change of 1 for a tree height increment
    ///     does not occur.
    /// </returns>
    private Int32 RotateOnce(bool left, LongVectorNode<T> parentNode, ref LongVectorNode<T> node)
    {
        // Obtain the node in the opposite direction. The rotate will pull-up the node one level and become the root
        // node of the subtree. The former root node is pushed down in the specified rotation direction.
        LongVectorNode<T> upNode = left? _rightSubnode: _leftSubnode;
        Debug.Assert(upNode != null);

        // Establish whether the rotation will decrement the height of the subtree.
        Int32 heightChange = upNode.Balance == 0? 0: -1;

        // Rotate. This transfers a subnode of the node that is pulled-up one level to the node that is pushed down a
        // level, being the current node.
        LongVectorNode<T> transferredNode = left? upNode._leftSubnode: upNode._rightSubnode;
        if (left)
        {
            upNode._leftSubnode = node;
        }
        else
        {
            upNode._rightSubnode = node;
        }
        node = upNode;
        if (left) // Use the opposite direction.
        {
            _rightSubnode = transferredNode;
        }
        else
        {
            _leftSubnode = transferredNode;
        }

        // Update the balances.
        upNode.AdjustBalance(1, left);
        Balance = -upNode.Balance;

        // Nodes refer to the parent node; let the nodes reflect the situation after the rotation. Update the node counts.
        upNode._parentNode = parentNode;
        _parentNode = upNode;
        long totalSubtreeCount = _count;
        _count -= upNode._count;
        if (transferredNode != null)
        {
            transferredNode._parentNode = left? upNode._leftSubnode: upNode._rightSubnode;
            _count += transferredNode._count;
        }
        Debug.Assert(_count != 0 && totalSubtreeCount != 0);
        upNode._count = totalSubtreeCount;

        return heightChange;
    }

    /// <summary>Corrects an inbalance by performing a double rotation.</summary>
    /// <remarks>The double rotation decrements the height of the subtree in all cases.</remarks>
    /// <param name="left">I: True if the subnode direction is left, false if right.</param>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: Node.</param>
    /// <returns>
    ///     The method returns the change of height of the current tree. A double rotation always decrements the height
    ///     and hence the return value is always -1.
    /// </returns>
    private Int32 RotateTwice(bool left, LongVectorNode<T> parentNode, ref LongVectorNode<T> node)
    {
        // Obtain the node that is neither pulled-up a level nor pushed down a level; the steady node.
        LongVectorNode<T> steadyNode = left? _rightSubnode: _leftSubnode; // Opposite direction.
        Debug.Assert(steadyNode != null);

        // Obtain the node that becomes the new root node of the subtree. The node is present under the steady node and
        // is pulled-up two levels.
        LongVectorNode<T> upNode = left? steadyNode._leftSubnode: steadyNode._rightSubnode;
        Debug.Assert(upNode != null);

        // Rotate. This transfers the two subnodes of the node that is pulled-up two levels. One subnode is transferred
        // to the former rootnode, being the current node, that is pushed-down one level. The other subnode is
        // transferred to the steady node.
        LongVectorNode<T> downNode = node;
        node = upNode;
        LongVectorNode<T> transferredNodeDirection = left? upNode._leftSubnode: upNode._rightSubnode;
        LongVectorNode<T> transferredNodeOppositeDirection = left? upNode._rightSubnode: upNode._leftSubnode;
        if (left)
        {
            upNode._leftSubnode = downNode;
            upNode._rightSubnode = steadyNode;
            _rightSubnode = transferredNodeDirection;
            steadyNode._leftSubnode = transferredNodeOppositeDirection;
        }
        else
        {
            upNode._rightSubnode = downNode;
            upNode._leftSubnode = steadyNode;
            _leftSubnode = transferredNodeDirection;
            steadyNode._rightSubnode = transferredNodeOppositeDirection;
        }

        // Update the balances.
        if (left)
        {
            Balance = -Math.Max(upNode.Balance, 0);
            steadyNode.Balance = -Math.Min(upNode.Balance, 0);
        }
        else
        {
            steadyNode.Balance = -Math.Max(upNode.Balance, 0);
            Balance = -Math.Min(upNode.Balance, 0);
        }
        upNode.Balance = 0;

        // Nodes refer to the parent node; let the nodes reflect the situation after the rotation. Update the node counts.
        upNode._parentNode = parentNode;
        _parentNode = upNode;
        steadyNode._parentNode = upNode;
        long totalSubtreeCount = _count;
        _count -= steadyNode._count;
        if (transferredNodeDirection != null)
        {
            transferredNodeDirection._parentNode = downNode;
            _count += transferredNodeDirection._count;
        }
        steadyNode._count -= upNode._count;
        if (transferredNodeOppositeDirection != null)
        {
            transferredNodeOppositeDirection._parentNode = steadyNode;
            steadyNode._count += transferredNodeOppositeDirection._count;
        }
        upNode._count = totalSubtreeCount;
        Debug.Assert(_count != 0 && steadyNode._count != 0 && upNode._count != 0);

        // A double rotation always decrements the height of the current tree.
        return -1;
    }

    /// <summary>Rebalances, if necessary.</summary>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="node">IO: This node.</param>
    /// <returns>
    ///     The method returns the change of height of the current tree. The change is -1 if the tree height is
    ///     decremented. The change is 0 if rebalancing was not necessary or if rebalancing did not decrement the
    ///     height. A change of 1 for an increment of the tree height does not occur.
    /// </returns>
    private Int32 Rebalance(LongVectorNode<T> parentNode, ref LongVectorNode<T> node)
    {
        Int32 heightChange;
        Int32 balance = Balance;
        if (balance == LeftImbalance)
        {
            Int32 leftBalance;
            if (_leftSubnode == null)
            {
                leftBalance = Balanced;
            }
            else
            {
                leftBalance = _leftSubnode.Balance;
            }
            if (leftBalance == RightHeavy)
            {
                heightChange = RotateTwice(false, parentNode, ref node);
            }
            else if (leftBalance == Balanced || leftBalance == LeftHeavy)
            {
                heightChange = RotateOnce(false, parentNode, ref node);
            }
            else
            {
                throw new Exception();
            }
        }
        else if (balance == RightImbalance)
        {
            Int32 rightBalance;
            if (_rightSubnode == null)
            {
                rightBalance = Balanced;
            }
            else
            {
                rightBalance = _rightSubnode.Balance;
            }
            if (rightBalance == LeftHeavy)
            {
                heightChange = RotateTwice(true, parentNode, ref node);
            }
            else if (rightBalance == Balanced || rightBalance == RightHeavy)
            {
                heightChange = RotateOnce(true, parentNode, ref node);
            }
            else
            {
                throw new Exception();
            }
        }
        else if (balance == LeftHeavy || balance == Balanced || balance == RightHeavy)
        {
            heightChange = 0;
        }
        else
        {
            throw new Exception();
        }
        return heightChange;
    }

    // Element access.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Returns the element at the specified index.</summary>
    /// <param name="index">I: Index, 0-based, must be valid.</param>
    /// <param name="leftSkipped">I: Number of elements skipped in nodes and subtrees on the left.</param>
    internal LongVectorNode<T> GetNode(long index, long leftSkipped)
    {
        long currentIndex = leftSkipped;
        if (_leftSubnode != null)
        {
            currentIndex += _leftSubnode._count;
        }
        LongVectorNode<T> node;
        if (index < currentIndex)
        {
            Debug.Assert(_leftSubnode != null);
            node = _leftSubnode.GetNode(index, leftSkipped);
        }
        else if (index > currentIndex)
        {
            Debug.Assert(_rightSubnode != null);
            if (_leftSubnode != null)
            {
                leftSkipped += _leftSubnode._count;
            }
            node = _rightSubnode.GetNode(index, leftSkipped + 1);
        }
        else
        {
            node = this;
        }
        return node;
    }

    /// <summary>Searches the vector for the element and returns the index of the found element.</summary>
    /// <remarks>The method performs a binary search.</remarks>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="comparer">I: Comparer.</param>
    /// <param name="leftSkipped">I: Number of elements skipped in nodes and subtrees on the left.</param>
    /// <returns>
    ///     Index, 0-based, or a negative number of the element is not found. The negative number is the bitwise
    ///     complement of the index of the next element that is larger than element or, if there is no larger element, the
    ///     bitwise complement of the vector count.
    /// </returns>
    internal long BinarySearch(T element, IComparer<T> comparer, long leftSkipped)
    {
        Int32 compareResult = comparer.Compare(element, _element);
        long index;
        if (compareResult < 0)
        {
            if (_leftSubnode == null)
            {
                index = ~leftSkipped;
            }
            else
            {
                index = _leftSubnode.BinarySearch(element, comparer, leftSkipped);
            }
        }
        else if (compareResult > 0)
        {
            if (_rightSubnode == null)
            {
                leftSkipped += _count;
                index = ~leftSkipped;
            }
            else
            {
                if (_leftSubnode != null)
                {
                    leftSkipped += _leftSubnode._count;
                }
                leftSkipped++;
                index = _rightSubnode.BinarySearch(element, comparer, leftSkipped);
            }
        }
        else
        {
            if (_leftSubnode != null)
            {
                leftSkipped += _leftSubnode._count;
            }
            index = leftSkipped;
        }
        return index;
    }

    /// <summary>Searches the vector for the element and returns the index of the found element.</summary>
    /// <remarks>The method performs a binary search. The method searches the specified range only.</remarks>
    /// <param name="rangeIndex">I: Starting index of the range to search, 0-based.</param>
    /// <param name="rangeCount">I: Length of the range to search.</param>
    /// <param name="element">I: Element to look for.</param>
    /// <param name="comparer">I: Comparer.</param>
    /// <param name="leftSkipped">I: Number of elements skipped in nodes and subtrees on the left.</param>
    /// <returns>
    ///     Index, 0-based, or a negative number of the element is not found. The negative number is the bitwise
    ///     complement of the index of the next element that is larger than element or, if there is no larger element,
    ///     the bitwise complement of the vector count.
    /// </returns>
    internal long BinarySearch(long rangeIndex, long rangeCount, T element, IComparer<T> comparer, long leftSkipped)
    {
        long leftCount = _leftSubnode == null? 0: _leftSubnode._count;
        long currentIndex = leftSkipped + leftCount;
        long index;
        if (currentIndex < rangeIndex)
        {
            // Before the target range; continue walking towards the end of the vector.
            if (_rightSubnode == null)
            {
                index = ~rangeIndex;
            }
            else
            {
                index = _rightSubnode.BinarySearch(rangeIndex, rangeCount, element, comparer, leftSkipped + leftCount + 1);
            }
        }
        else if (currentIndex >= rangeIndex && currentIndex < rangeIndex + rangeCount)
        {
            // In the target range; switch to the actual binary search.
            Int32 compareResult = comparer.Compare(element, _element);
            if (compareResult < 0)
            {
                if (_leftSubnode == null)
                {
                    index = ~currentIndex;
                }
                else
                {
                    index = _leftSubnode.BinarySearch(rangeIndex, rangeCount, element, comparer, leftSkipped);
                }
            }
            else if (compareResult > 0)
            {
                if (_rightSubnode == null)
                {
                    index = ~(leftSkipped + _count);
                }
                else
                {
                    index = _rightSubnode.BinarySearch(rangeIndex, rangeCount, element, comparer, leftSkipped + leftCount + 1);
                }
            }
            else
            {
                index = leftSkipped + leftCount;
            }
        }
        else
        {
            // Beyond the target range; invert the direction of the walk and start walking towards the begin of the vector.
            if (_leftSubnode == null)
            {
                index = ~(rangeIndex + rangeCount);
            }
            else
            {
                index = _leftSubnode.BinarySearch(rangeIndex, rangeCount, element, comparer, leftSkipped);
            }
        }
        return index;
    }

    /// <summary>Copies nodes recursively.</summary>
    /// <param name="from">I: Node to copy-convert, or null.</param>
    /// <param name="to">IO: Reference that will be set with a copied node, or that remains null.</param>
    internal static void CopyAll(LongVectorNode<T> from, ref LongVectorNode<T> to)
    {
        if (from != null)
        {
            Debug.Assert(to == null);
            to = new LongVectorNode<T>();
            to._count = from._count;
            to._element = from._element;
            to._flags = from._flags;
            CopyAll(from._leftSubnode, ref to._leftSubnode);
            CopyAll(from._rightSubnode, ref to._rightSubnode);
        }
    }

    /// <summary>Copies nodes recursively, converting the element values from the input type to the output type.</summary>
    /// <typeparam name="TOutput">I: The type of the elements in the target vector.</typeparam>
    /// <param name="from">I: Node to copy-convert, or null.</param>
    /// <param name="converter">I: Delegate that performs the element conversion.</param>
    /// <param name="to">IO: Reference that will be set with a copied node, or that remains null.</param>
    internal static void ConvertAll<TOutput>(LongVectorNode<T> from, Converter<T, TOutput> converter, ref LongVectorNode<TOutput> to)
    {
        if (from != null)
        {
            Debug.Assert(to == null);
            to = new LongVectorNode<TOutput>();
            to._count = from._count;
            to._element = converter(from._element);
            to._flags = from._flags;
            ConvertAll(from._leftSubnode, converter, ref to._leftSubnode);
            ConvertAll(from._rightSubnode, converter, ref to._rightSubnode);
        }
    }

    /// <summary>Returns a reference to the next node in the vector order.</summary>
    /// <returns>Returns null if there is no next node.</returns>
    public LongVectorNode<T> GetNext()
    {
        LongVectorNode<T> node = this;
        if (_rightSubnode == null)
        {
            LongVectorNode<T> parentNode = _parentNode;
            while (parentNode != null && ReferenceEquals(parentNode._rightSubnode, node))
            {
                node = parentNode;
                parentNode = node._parentNode;
            }
            if (parentNode != null && ReferenceEquals(parentNode._leftSubnode, node))
            {
                node = parentNode;
            }
            else
            {
                node = null;
            }
        }
        else
        {
            node = node._rightSubnode;
            while (node._leftSubnode != null)
            {
                node = node._leftSubnode;
            }
        }
        return node;
    }

    /// <summary>Returns a reference to the previous node in the vector order.</summary>
    /// <returns>Returns null if there is no previous node.</returns>
    public LongVectorNode<T> GetPrevious()
    {
        LongVectorNode<T> node = this;
        if (_leftSubnode == null)
        {
            LongVectorNode<T> parentNode = _parentNode;
            while (parentNode != null && ReferenceEquals(parentNode._leftSubnode, node))
            {
                node = parentNode;
                parentNode = node._parentNode;
            }
            if (parentNode != null && ReferenceEquals(parentNode._rightSubnode, node))
            {
                node = parentNode;
            }
            else
            {
                node = null;
            }
        }
        else
        {
            node = node._leftSubnode;
            while (node._rightSubnode != null)
            {
                node = node._rightSubnode;
            }
        }
        return node;
    }

    // Sort.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Builds a sorted vector by performing a sorted insert of the elements in the subtree started by the node.</summary>
    /// <param name="comparer">I: Comparer.</param>
    /// <param name="level">I: Current level, 0 initially, 1 for the root node.</param>
    /// <param name="targetLevel">I: Level to insert; 1 for the root node.</param>
    /// <param name="node">IO: Node starting a subtree.</param>
    /// <param name="vector">IO: Vector to build-up.</param>
    internal static void Sort(IComparer<T> comparer, Int32 level, Int32 targetLevel, ref LongVectorNode<T> node, LongVector<T> vector)
    {
        if (node != null)
        {
            level++;
            if (level == targetLevel)
            {
                // Use the binary search for a sorted insert.
                long index = vector.BinarySearch(node._element, comparer);
                if (index >= 0)
                {
                    // Element found; insert at the position of the element.
                    Debug.Assert(index < vector.LongCount);
                    vector.Insert(index, node._element);
                }
                else
                {
                    // Element not found. The index specifies the position of the next-greater element. Insert at that position.
                    index = ~index;
                    Debug.Assert(index >= 0 && index <= vector.LongCount);
                    vector.Insert(index, node._element);
                }
                // Set the element to its default value in order to set reference types to null as early as possible.
                node._element = default(T);
                // The target level is selected such that leaf nodes are visited first. Free this leaf node.
                Debug.Assert(node._leftSubnode == null && node._rightSubnode == null);
                node = null;
            }
            else
            {
                Debug.Assert(level < targetLevel);
                Sort(comparer, level, targetLevel, ref node._leftSubnode, vector);
                Sort(comparer, level, targetLevel, ref node._rightSubnode, vector);
            }
        }
    }

    // Test and debug support.
    // -----------------------------------------------------------------------------------------------------------------

    /// <summary>Dumps the vector.</summary>
    /// <param name="level">I: level.</param>
    internal void Dump(Int32 level)
    {
        string indent = string.Empty;
        long count = _count;
        for (Int32 i = 0; i != level; i++)
        {
            indent += "  ";
        }
        Int32 leftHeight = 0;
        Trace.WriteLine(string.Format("{0}{1} count {2} height {3}", indent, _element, _count, GetHeight()));
        indent += "  ";
        if (_leftSubnode == null)
        {
            Trace.WriteLine(string.Format("{0}Left null", (object) indent));
        }
        else
        {
            leftHeight = _leftSubnode.GetHeight();
            _leftSubnode.Dump(level + 1);
            count -= _leftSubnode._count;
        }
        Int32 rightHeight = 0;
        if (_rightSubnode == null)
        {
            Trace.WriteLine(string.Format("{0}Right null", indent));
        }
        else
        {
            rightHeight = _rightSubnode.GetHeight();
            _rightSubnode.Dump(level + 1);
            count -= _rightSubnode._count;
        }
        Debug.Assert(count == 1);
        Debug.Assert(Balance == 0 && leftHeight == rightHeight || Balance == -1 && leftHeight == rightHeight + 1 ||
            Balance == 1 && leftHeight + 1 == rightHeight);
        //
    }

    /// <summary>Establishes whether the subtree started by the node is consistent and whether the subtree is balanced.</summary>
    /// <remarks>This method is for white box test support.</remarks>
    /// <param name="parentNode">I: Parent node.</param>
    /// <param name="height">O: Height of the subtree started by the node.</param>
    /// <param name="count">O: Number of elements in the subtree.</param>
    internal bool GetConsistency(LongVectorNode<T> parentNode, out Int32 height, out long count)
    {
        Int32 leftHeight;
        long leftCount;
        if (_leftSubnode == null)
        {
            leftHeight = 0;
            leftCount = 0;
        }
        else
        {
            _leftSubnode.GetConsistency(this, out leftHeight, out leftCount);
        }
        Int32 rightHeight;
        long rightCount;
        if (_rightSubnode == null)
        {
            rightHeight = 0;
            rightCount = 0;
        }
        else
        {
            _rightSubnode.GetConsistency(this, out rightHeight, out rightCount);
        }
        height = 1 + Math.Max(leftHeight, rightHeight);
        count = 1 + leftCount + rightCount;
        return ReferenceEquals(_parentNode, parentNode) && count == _count && (leftHeight == rightHeight && Balance == 0 ||
            leftHeight + 1 == rightHeight && Balance == 1 || leftHeight == rightHeight + 1 && Balance == -1);
        //
    }
}

} // namespace
